An image usually contains a very large amount of information. To save the storage space and bandwidth for transmission, a highly efficient coding is employed for encoding image data when the image is stored or transmitted. For example, the image data is subjected to a Discrete Cosine Transformation (DCT) into DCT coefficients for each block in many compression techniques.
A Hadamard transform is a process associated with this DCT transformation or a process for transforming the image data. The Hadamard transform is an orthogonal transformation with a transformation matrix composed of the elements of “1” or “−1,” which is the simplest one that is represented only by addition and subtraction.
A Hadamard matrix HJ is a symmetric J×J matrix with elements +1 and −1. The Hadamard matrix of second order is given by:
      H    2    =                                                1                                1                                                1                                              -              1                                                  .  
Also, the Hadamard matrix of fourth order is given by:
      H    4    =                                                1                                1                                1                                1                                                1                                              -              1                                            1                                              -              1                                                            1                                1                                              -              1                                                          -              1                                                            1                                              -              1                                                          -              1                                            1                                      .  
The above Hadamard matrix is called a natural type, in which the base vectors are not arranged in sequence. Thus, if the permutation of the base vectors is repeated in order to shift the base vector in the second row to the fourth row, a Walsh type Hadamard matrix is obtained as follows wherein the base vectors are arranged in a sequence.
      H    4    =                                  1                          1                          1                          1                                      1                          1                                      -            1                                                -            1                                                1                                      -            1                                                -            1                                    1                                      1                                      -            1                                    1                                      -            1                                  
Hadamard matrices having an order other than powers of 2 do exist, but they are not widely used in image processing.
An inverse Hadamard matrix is easily computed as:
      H    J          -      1        =            1      J        ⁢          H      J      
Accordingly, the Hadamard transform is given by:
F=HMfH′N; and its inverse is also given by:
  f  =            1      MN        ⁢          H      M        ⁢                  FH        N        ′            .      
In practice, the encoding side usually has more resources available which can be used to process the image data, e.g., performing a Hadamard Transform. However, for the decoding side, especially some low-end applications such as a movable video player, a mobile phone, etc., useable resources are very limited, and thus how the Inverse Hadamard Transform can be performed becomes an important problem.
If in the decoding side, the Inverse Hadamard Transform (IHT) is performed by software, the processor load and usage of the memory of the decoding device will increase and the performance will be degraded greatly. Currently, there are some hardware apparatuses implemented as the IHT converters, for example, for the standard of Advanced Video Coding (AVC) standard also known as H.264. However, the IHT conversions are realized in a chip by having a lot of adders and registers, which will lead to the area of the chip being enlarged, and thus, the cost increases.
Therefore, what is needed is an IHT device that can achieve a good balance between the cost and the performance.